import math
Hx=0
m = []
code_k=[]
x= eval(input('请键入符号：'))
y= eval(input('请键入符号概率：'))
arr = [[x[i], y[i]] for i in range(len(x))]
tree = {}

def code_length():#码字长度
    list_code = list(code)
    for i in range(len(list_code)):
        code_k.append(len(code[x[i]]))
    return code_k


def H():#信源熵
    global Hx
    for i in range(len(x)):
        Hx += y[i] * math.log(y[i], 2) * (-1)
    return Hx

def huffmanB(root, tree, rootCode='', codeDict={}, depth=1, res=0):#求编码
    # 对左子树进行处理
    if len(root['left'][0]) == 1:
        codeDict[root['left'][0]] = '0' + rootCode
        res += (len(rootCode) + 1) * root['left'][1]
    else:
        codeDict, res = huffmanB(tree[root['left'][0]], tree, '0' + rootCode, codeDict, depth + 1, res)

    # 对右子树进行处理
    if len(root['right'][0]) == 1:
        codeDict[root['right'][0]] = '1' + rootCode
        res += (len(rootCode) + 1) * root['right'][1]  # 计算平均位数
    else:
        codeDict, res = huffmanB(tree[root['right'][0]], tree, '1' + rootCode, codeDict, depth + 1, res)

    return codeDict, res


while len(arr) > 1:
    arr.sort(key=lambda u: u[1])
    #选出最小的两个节点
    l = arr[0]  # 较小的作为左子树
    r = arr[1]  # 较大者作为右子树

    if len(arr) > 2:
        tree[l[0] + r[0]] = {'left': l, 'right': r}

        #用新节点置换这两个节点
        arr = arr[2:]
        arr.append([l[0] + r[0], l[1] + r[1]])
    else:
        tree['root'] = {'left': l, 'right': r}
        break

def eff():#编码效率
    e = Hx / round(res/sum(y),3)
    return e

def ave_code():#平均码长
    length_k=res / sum(y)
    return length_k

def codeword():#对应码字
    for i in range(len(x)):
        u = str(code[x[i]].replace('1', '2'))
        n = u.replace('0', '1')
        s = n.replace('2', '0')
        b = list(s)
        b.reverse()
        m.append(''.join(b))
    return m

def PrintArr():#打印各类数组结果
    print('码长：{}'.format(code_k))
    print('平均码长：{:.3}(bin/symbol)'.format(ave_code()))
    print('各字符码字为：{}'.format(codeword()))
    print('信源熵：{:.3}(bit/symbol)'.format(Hx))
    print('编码效率为：{:.2%}'.format(eff()))

#调用函数开始执行
code, res = huffmanB(tree['root'], tree)
code_length()
H()
PrintArr()

